package com.computer.fundamentals.algorithm;

import java.util.*;

/**
 * 拓扑排序
 * 背景知识：
 *      一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。
 *      在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，
 *      也就是说，一个子工程的开始是以它的所有前序子工程的结束为先决条件的，但有些子工程没有先决条件，可以安排在任何时间开始。
 *      为了形象地反映出整个工程中各个子工程(活动)之间的先后关系，可用一个有向图来表示，图中的顶点代表活动(子工程)，
 *      图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行。
 *      通常，我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称AOV网。
 *  定义：
 *      在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，
 *      使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列(Topological order)
 */
public class TopologicalSort {

    /**
     * 以经典问题——课程表(LeetCoe.207)为例
     * @param numCourses 课程数量
     * @param prerequisites 课程安排先决条件
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 数据量大的时候建议使用List，因为此处课程号完全和列表下标对应，但缺点是需要多跑一次循环添加空列表
        // 数据量小的时候建议使用HashMap，冲突的概率较小，可以减少一次循环添加列表的开销
        Map<Integer, List<Integer>> adjacency = new HashMap<>();
        int[] inDegree = new int[numCourses];
        for (int[] prerequisite : prerequisites) {
            int cur = prerequisite[0];
            int pre = prerequisite[1];
            if (adjacency.containsKey(pre)) {
                adjacency.get(pre).add(cur);
            } else {
                List<Integer> nodeList = new ArrayList<>();
                nodeList.add(cur);
                adjacency.put(pre, nodeList);
            }
            inDegree[cur]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0;i < numCourses;i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            int n = queue.size();
            for (int i = 0;i < n;i++) {
                Integer node = queue.poll();
                List<Integer> tmp = adjacency.get(node);
                numCourses--;
                if (tmp == null) {
                    continue;
                }
                for (Integer integer : tmp) {
                    inDegree[integer]--;
                    if (inDegree[integer] == 0) {
                        queue.offer(integer);
                    }
                }
            }
        }

        return numCourses == 0;
    }

    /**
     * 测试，详细测试前往 https://leetcode-cn.com/problems/course-schedule/
     */
    public static void main(String[] args) {

        TopologicalSort topologicalSort = new TopologicalSort();
        System.out.println("------------滑动窗口测试------------");
        boolean res = topologicalSort.canFinish(2, new int[][]{{1, 0}, {0, 1}});
        System.out.println(res);

    }
}